#include <cstddef>
#include <iostream>
template <typename T>
class Allocator {
public:
    T* allocate(size_t size) {
        return (T*)malloc(sizeof(T) * size);
    }

    void deallocate(T* p) {
        free(p);
    }

    void construct(T* p, const T& val) {
        new (p) T(val);  // placement new
    }

    void destroy(T* p) {
        p->~T();
    }
};

template <typename T, typename Alloc = Allocator<T>>
class Vector {
public:
    Vector(size_t size = 10) {
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }
    ~Vector() {
        size_t len = _last - _first;
        for (int i = 0; i < len; i++) {
            _allocator.destroy(_first + i);
        }

        _allocator.deallocate(_first);
        _first = _last = _end = nullptr;
    }
    Vector(const Vector<T>& other) {
        size_t len = other._last - other._first;
        size_t cap = other._end - other._first;
        _first = _allocator.allocate(cap);
        for (int i = 0; i < len; i++) {
            _allocator.construct(_first + i, other._first[i]);
        }

        _last = _first + len;
        _end = _first + cap;
    }

    Vector(Vector<T>&& other) {
        _first = other._first;
        _last = other._last;
        _end = other._end;
        other._first = other._last = other._end = nullptr;
    }

    Vector<T>& operator=(const Vector<T>& other) {
        if (this == &other) return *this;

        size_t len = _last - _first;
        for (int i = 0; i < len; i++) {
            _allocator.destroy(_first + i);
        }

        _allocator.deallocate(_first);

        len = other._last - other._first;
        size_t cap = other._end - other._first;
        _first = _allocator.allocate(cap);
        for (int i = 0; i < len; i++) {
            _allocator.construct(_first + i, other._first[i]);
        }

        _last = _first + len;
        _end = _first + cap;
        return *this;
    }

    Vector<T>& operator=(Vector<T>&& other) {
        if (this == &other) return *this;

        size_t len = _last - _first;
        for (int i = 0; i < len; i++) {
            _allocator.destroy(_first + i);
        }

        _allocator.deallocate(_first);

        _first = other._first;
        _last = other._last;
        _end = other._end;
        other._first = other._last = other._end = nullptr;
        return *this;
    }

    class iterator;
    iterator begin() {
        return iterator(_first);
    }
    iterator end() {
        return iterator(_last);
    }
    class iterator {
    public:
        iterator(T* p) : _p(p) {
        }

        bool operator!=(const iterator& other) const{
            return _p != other._p;
        }

        bool operator<(const iterator& other) const{
            return _p < other._p;
        }

        bool operator>(const iterator& other) const{
            return _p > other._p;
        }

        bool operator<=(const iterator& other) const{
            return _p <= other._p;
        }

        bool operator>=(const iterator& other) const{
            return _p >= other._p;
        }

        bool operator==(const iterator& other) const{
            return _p == other._p;
        }

        iterator& operator++() {
            ++_p;
            return *this;
        }

        iterator operator++(int) {
            iterator tmp(*this);
            _p++;
            return tmp;
        }

        iterator& operator--() {
            --_p;
            return *this;
        }

        iterator operator--(int) {
            iterator tmp(*this);
            _p--;
            return tmp;
        }

        T& operator*() {
            return *_p;
        }

        T* operator->() {
            return _p;
        }

        const T& operator*() const {
            return *_p;
        }

    private:
        T* _p;
    };

public:
    void push_back(const T& val) {
        if (_last == _end) resize();
        _allocator.construct(_last, val);
        ++_last;
    }

    void pop_back() {
        if (_last == _first) {
            return;
        }
        _allocator.destroy(_last - 1);
        --_last;
    }

    T back() const {
        return *(_last - 1);
    }

    bool empty() const {
        return _last == _first;
    }

    size_t size() const {
        return _last - _first;
    }

    T& operator[](size_t idx) {
        return _first[idx];
    }

    const T& operator[](size_t idx) const {
        return _first[idx];
    }

private:
    void resize() {
        size_t cap = _end - _first;
        size_t len = _last - _first;
        size_t newcap = cap * 2;
        T* ptmp = _allocator.allocate(newcap);
        for (size_t i = 0; i < len; i++) {
            _allocator.construct(ptmp + i, _first[i]);
            _allocator.destroy(_first + i);
        }

        _allocator.deallocate(_first);

        _first = ptmp;
        _last = _first + len;
        _end = _first + newcap;
    }

private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _allocator;
};

class Foo {
public:
    Foo(int a = 0) : _a(a) {
        std::cout << "Foo()" << std::endl;
    }
    ~Foo() {
        std::cout << "~Foo()" << std::endl;
    }
    Foo(const Foo& other) : _a(other._a) {
        std::cout << "Foo(const Foo&)" << std::endl;
    }
    Foo(Foo&& other) : _a(other._a) {
        other._a = -1;
        std::cout << "Foo(Foo&&)" << std::endl;
    }

    int a() const {
        return _a;
    }

private:
    int _a;
};

std::ostream& operator<<(std::ostream& os, const Foo& val) {
    os << val.a();
    return os;
}

int main() {
    Foo f;
    Vector<Foo> v(2);
    v.push_back(Foo(1));
    v.push_back(Foo{2});
    v.push_back({3});
    v.push_back(4);
    std::cout << "==================" << std::endl;

    Vector<Foo> v2(v);
    for (auto &f : v2) {
        std::cout << f << " ";
    }
    std::cout << std::endl;
    std::cout << "==================" << std::endl;

    Vector<Foo> v3(std::move(v2));
    std::cout << v2.empty() << std::endl;

    std::cout << v3[0].a() << std::endl;
    std::cout << v3.begin()->a() << std::endl;
    std::cout << "==================" << std::endl;


    while (!v.empty()) {
        std::cout << v.back() << " ";
        v.pop_back();
    }
}
